//递归和非递归分别实现strlen

#include <stdio.h>

//非递归指针
size_t my_strlen1(const char* str)
{
    size_t count = 0;
    const char* s = str;
    while(*s)
    {
        count++;
        s++;
    }
    return count;
}

//递归实现

size_t my_strlen(const char* str)
{
    const char* s = str;
    if(*s == '\0')
        return 0;
    return 1 + my_strlen(++s);
}

int main1()
{
    const char* s = "hello 1";
    printf("%zd\n", my_strlen(s));
    return 0;
}

/*
编写一个函数 reverse_string(char * string)（递归实现）
实现：将参数字符串中的字符反向排列，不是逆序打印。
要求：不能使用C函数库中的字符串操作函数。
比如:
char arr[] = "abcdef";
逆序之后数组的内容变成：fedcba
*/

#include <string.h>

//非递归
void reverse_string1(char* string)
{
    int len = (int)strlen(string);
    int left = 0;
    int right = len - 1;
    while(left < right)
    {
        char tmp = string[left];
        string[left] = string[right];
        string[right] = tmp;

        left++;
        right--;
    }
}   


//递归版本
void reverse_helper(char* string, int left, int right)
{
    if(left >= right)
    {
        return;
    }
    char tmp = string[left];
    string[left] = string[right];
    string[right] = tmp;

    reverse_helper(string, left+1, right-1);
}
void reverse_string(char* string)
{
    int len = 0;
    while(string[len] != '\0')
    {
        len++;
    }
    reverse_helper(string, 0, len-1);
}
int main2()
{
    char str[] = {"abcdefg"};
    reverse_string(str);
    puts(str);
    return 0;
}

/*
写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19
输入：1729，输出：19

*/

int DigitSum1(int n)
{
    int count = n % 10;
    while(n /= 10)
    {
        count += (n % 10);
    }
    return count;
}
//递归
int DigitSum(int n)
{
    //int count = 0;
    if(n/10 == 0)
    {
        return n;
    }
    return (n%10) + DigitSum(n / 10);
}
int main3()
{
    int a = 0;
    scanf("%d", &a);
    printf("%d\n",DigitSum(a));

    return 0;
}

/*
编写一个函数实现n的k次方，使用递归实现。
*/
int pow_k1(int n, int k)
{
    int ret = 1;
    while(k)
    {
        ret = ret * n;
        k--;
    }
    return ret;
}

//递归
int pow_k(int n, int k)
{
    if(k == 0)
        return 1;
    return n * pow_k(n, k -1);
}

int main4()
{
    int n,k;
    scanf("%d %d", &n, &k);
    printf("%d\n", pow_k(n, k));
    return 0;
}

/*
递归和非递归分别实现求第n个斐波那契数
例如：
输入：5  输出：5
输入：10， 输出：55
输入：2， 输出：1
*/
int fac1(int n)
{
    if(n == 0) return 0;
    int start = 1;
    int end = 1;
    int ret = end;
    while(n-2)
    {
        ret = start + ret;
        start = end;
        end = ret;
        n--;
    }
    return ret;
}
//递归
int fac(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;

    return fac(n - 1) + fac(n - 2);
}
int main5()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", fac(n));
    return 0;
}

//实现一个对整形数组的冒泡排序

void bubble_sort(int arr[], int len)
{
    int i = 0;
    for(i = 0; i < len - 1; i++)
    {
        int j = 0;
        for(j = 0; j < len - i - 1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}
int main6()
{
    int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    int len = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, len);
    int i = 0;
    for(i = 0; i < len; i ++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

/*
创建一个整形数组，完成对数组的操作
实现函数init() 初始化数组为全0
实现print()  打印数组的每个元素
实现reverse()  函数完成数组元素的逆置。
要求：自己设计以上函数的参数，返回值。
*/

void init(int arr[], int len)
{
    int i = 0;
    for(i = 0; i < len; i++)
    {
        arr[i] = 0;
    }
}
void print(int arr[], int len)
{
    int i = 0;
    for(i = 0; i < len; i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
void reverse(int arr[], int len)
{
    int left = 0;
    int right = len - 1;
    while(left <= right)
    {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;

        left++;
        right--;
    }
}

int main7()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int len = sizeof(arr)/sizeof(arr[0]);
    //init(arr, len);
    print(arr, len);
    reverse(arr, len);
    print(arr, len);
    return 0;
}

//将数组A中的内容和数组B中的内容进行交换。（数组一样大）

void my_mecopy(char* dest, char* src)
{
    while((*dest++ = *src++) != '\0');
}
int main8()
{
    char arr1[5] = "hello";
    char arr2[] = { 0 };
    int i = 0;
    for(i = 0; i < 5; i++)
    {
        printf("%c ",arr1[i]);
    }
    printf("\n");
    my_mecopy(arr2, arr1);
    for(i = 0; i < 5; i++)
    {
        printf("%c ",arr2[i]);
    }
    printf("\n");

}


/*
编程实现：两个int（32位）整数m和n的二进制表达中，有多少个位(bit)不同？ 
输入例子:
1999 2299
输出例子:7
*/
#include <stdio.h>
int main9() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to 
    int n = a^b;//
    int count = 0;
    // 8 9
    // 1000
    // 1001
    // 1110

    // 1110
    //-0001
    //=1101
    //&1110
    //=1100
    while(n)
    {
        count++;
        n = n & (n - 1);
    }
    printf("%d", count);
    }
    return 0;
}

//获取一个整数二进制序列中所有的偶数位和奇数位，分别打印出二进制序列
//

//   1011 0010
//偶：1101
//奇：0100
void Func(int n)
{
	//奇数位
    int i = 0;
	for (i = 30;i >= 0;i -= 2)
	{
		printf("%d ",(n >> i) & 1);
	}
	printf("\n");

	for (i = 31; i >= 1; i -= 2)
	{
		printf("%d ", (n >> i) & 1);
	}
}
int main10()
{
//    /*
    char arr[32] = {0};
    int n = 0;
    scanf("%d", &n);
    int i = 0;
    if(n < 0) //负数的符号位是1；
        arr[0] = 1;
    else
        arr[0] = 0;
    for(i = 31; i > 0; i--)
    {
        /*
        if(n & (1 << 31 - i))
            arr[i] = '1';
        else
            arr[i] = '0';
        */
       //arr[31] = 32位 = n >> 0 & 1 
       arr[i] = (n >> (31-i)) & 1;
    }
    //int i = 0;
    for(i = 0; i < 32; i+=2)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    for(i = 1; i < 32; i+=2)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
//    */
    Func(-123);
    return 0;
}

//不允许创建临时变量，交换两个整数的内容

// 0 ^ b = b
// b ^ b = 0
// a b
// a = a^b;
// b = a^b === a^b^b
// a = a^b === a^a^b
// 3 5
// a b
//a = 3^5
//a = 3^5^5 = 
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    a = a^b;
    b = a^b;
    a = a^b;
    printf("%d %d\n", a, b);
    return 0;
}